Linear Linked Structures¶
What Are Linked Structures?
The Unordered Linked List
The Ordered Linked List
Other types of Linked list
4.2 What Are Linked Structures?¶
Throughout the discussion of basic data structures, we implemented a dynamic array (ArrayList) on top of raw C++ arrays. However, other types of data structure exist — this chapter builds collections out of nodes and pointers instead of contiguous memory.
A list is a collection of items where each item holds a relative position with respect to the others. More specifically, we will refer to this type of list as an unordered list. We can consider the list as having a first item, a second item, a third item, and so on. For simplicity we will assume that lists cannot contain duplicate items.
The Unordered List Abstract Data Type¶
The structure of an unordered list is a collection of items where each item holds a relative position with respect to the others. Some possible unordered list operations are given below:
UnorderedList()constructs an empty list.isEmpty()tests whetherhead == NULL.add(item)inserts at the head in $O(1)$ time.
size()returns the number of items.search(item)returns whether the item occurs.remove(item)unlinks the first matching item. In this course implementation, a missing item leaves the list unchanged; it does not throw.
append(item)adds a new item to the end of the list making it the last item in the collection. It needs the item and returns nothing. Assume the item is not already in the list.index(item)returns the position of item in the list. It needs the item and returns the index. Assume the item is in the list.
insert(pos, item)adds a new item to the list at position pos. It needs the item and returns nothing. Assume the item is not already in the list and there are enough existing items to have position pos.pop()removes and returns the last item in the list. It needs nothing and returns an item. Assume the list has at least one item.pop(pos)removes and returns the item at position pos. It needs the position and returns the item. Assume the item is in the list.
4.3 Implementing an Unordered Linked List¶
In order to implement an unordered list, we will construct what is commonly known as a linked list. Recall that we need to be sure that we can maintain the relative positioning of the items. However, there is no requirement that we maintain that positioning in contiguous memory.
For example, consider the collection of items. It appears that these values have been placed randomly.
If we can maintain some explicit information in each item, namely the location of the next item, then the relative position of each item can be expressed by simply following the link from one item to the next.
It is important to note that the location of the first item of the list must be explicitly specified. Once we know where the first item is, the first item can tell us where the second is, and so on. The external pointer is often referred to as the head of the list. Similarly, the last item needs to know that there is no next item.
4.4 The Node Class¶
The basic building block for the linked list implementation is the node. Each node object must hold at least two pieces of information. First, the node must contain the list item itself. We will call this the data field of the node. In addition, each node must hold a pointer to the next node.
template <typename T>
class Node {
private:
T data; // data of generic type
Node<T> *next; // pointer to the next node
public:
Node(T initdata) {
data = initdata;
next = NULL;
}
T getData() const {
return data;
}
Node<T> *getNext() const {
return next;
}
void setData(T newData) {
data = newData;
}
void setNext(Node<T> *newnext) {
next = newnext;
}
};
The fields data and next are private. All client and list code must use
getData(), getNext(), setData(), and setNext(); direct access such as
node->next is intentionally illegal.
We create Node objects in the usual way.
#include <iostream>
#include "pythonds3/cppds/linked_list.hpp" // Node / UnorderedList / OrderedList
using namespace std;
int main() {
Node<int> *temp = new Node<int>(93);
cout << temp->getData() << endl;
cout << temp->getNext() << endl; // NULL prints as 0
delete temp;
return 0;
}
93
0
The special C++ pointer value NULL will play an important role in the Node class and later in the linked list itself. A pointer equal to NULL denotes the fact that there is no next node.
Note in the constructor that a node is initially created with next set to NULL. It is always a good idea to explicitly assign NULL to your initial pointer values — an uninitialized pointer contains garbage!
4.5 The Unordered Linked List Class¶
The unordered list will be built from a collection of nodes, each linked to the next by explicit pointers. With this in mind, the UnorderedList class must maintain a pointer to the first node. Code below shows the constructor. Note that each list object will maintain a single pointer to the head of the list.
template <typename T>
class UnorderedList {
private:
Node<T> *head;
public:
UnorderedList() {
head = NULL;
}
};
An empty list is created with UnorderedList<int> myList; — the constructor sets head to NULL, so the list starts with no nodes.
The assignment statement creates the linked list representation
As we discussed in the Node class, the special pointer NULL will again be used to state that the head of the list does not refer to anything. Eventually, the example list given earlier will be represented by a linked list as shown below:
The head of the list refers to the first node which contains the first item of the list. In turn, that node holds a pointer to the next node (the next item), and so on.
It is very important to note that the UnorderedList class itself does not contain any node objects. Instead it contains a single pointer to only the first node in the linked structure.
isEmpty() checks whether head == NULL; it returns true exactly when the list has no nodes.
bool isEmpty() const {
return head == NULL;
}
So how do we get items into our list? We need to implement the add() method. However, before we can do that, we need to address the important question of where in the linked list to place the new item.
Since this list is unordered, the specific location of the new item with respect to the other items already in the list is not important. The new item can go anywhere. With that in mind, it makes sense to place the new item in the easiest location possible.
Recall that the linked list structure provides us with only one entry point, the head of the list. All of the other nodes can only be reached by accessing the first node and then following next links. This means that the easiest place to add the new node is right at the head, or beginning, of the list
myList.add(31);
myList.add(77);
myList.add(17);
myList.add(93);
myList.add(26);
myList.add(54);
Note that since 31 is the first item added to the list, it will eventually be the last node on the linked list as every other item is added ahead of it. Also, since 54 is the last item added, it will become the data value in the first node of the linked list.
Therefore, we can create a new node and places the item as its data. Now we must complete the process by linking the new node into the existing structure.
void add(T item) {
Node<T> *temp = new Node<T>(item);
temp->setNext(head);
head = temp;
}
The order of the two steps described above is very important. What happens if the order of line 3 and line 4 is reversed?
Since the head was the only external pointer to the list nodes, all of the original nodes are lost and can no longer be accessed.
The next methods that we will implement – size(), search(), and remove() – are all based on a technique known as linked list traversal. Traversal refers to the process of systematically visiting each node.
To do this we use an external pointer that starts at the first node in the list. As we visit each node, we move the pointer to the next node by "traversing" the next pointer.
To implement the size() method, we need to traverse the linked list and keep a count of the number of nodes that occurred.
int size() const {
Node<T> *current = head;
int count = 0;
while (current != NULL) {
count++;
current = current->getNext();
}
return count;
}
Searching for a value in a linked list implementation of an unordered list also uses the traversal technique. As we visit each node in the linked list we will ask whether the data stored there matches the item we are looking for.
bool search(T item) const {
Node<T> *current = head;
while (current != NULL) {
if (current->getData() == item) {
return true;
}
current = current->getNext();
}
return false;
}
If we do get to the end of the list, that means that the item we are looking for must not be present. Also, if we do find the item, there is no need to continue.
myList.search(17)
Since 17 is present, traversal stops at that node and search(17) returns true.
remove() first traverses to the first matching node, then unlinks and deletes
that node. The public contract used by linked_list.hpp is erase-if-found:
if the value is absent, the list is unchanged. Removing the head and removing
an interior node require different pointer updates.
The first step is very similar to search. Starting with an external pointer set to the head of the list, we traverse the links until we discover the item we are looking for.
When the item is found and we break out of the loop, current will be a pointer to the node containing the item to be removed. But how do we remove it?
In order to remove the node containing the item, we need to modify the link in the previous node so that it refers to the node that comes after current. Unfortunately, there is no way to go backward in the linked list. Since current refers to the node ahead of the node where we would like to make the change, it is too late to make the necessary modification!
The solution to this dilemma is to use two external pointers as we traverse down the linked list. current will behave just as it did before, marking the current location of the traversal. The new pointer, which we will call previous, will always travel one node behind current. That way, when current stops at the node to be removed, previous will refer to the proper place in the linked list for the modification!
void remove(T item) {
Node<T> *current = head;
Node<T> *previous = NULL;
bool found = false;
// Step 1: traverse to find the item
while (!found && current != NULL) {
if (current->getData() == item) {
found = true;
} else {
previous = current;
current = current->getNext();
}
}
// Step 2: unlink and FREE the node (C++ has no garbage collector!)
if (found) {
if (previous == NULL) {
head = current->getNext();
} else {
previous->setNext(current->getNext());
}
delete current;
}
}
After unlinking a node, the class must delete it. The destructor applies the same rule to every remaining node owned by the list.
Figure below shows the movement of previous and current as they progress down the list looking for the node containing the value 17.
Once the searching step of the remove has been completed, we need to remove the node from the linked list. Figure above shows the link that must be modified.
However, there is a special case that needs to be addressed. If the item to be removed happens to be the first item in the list, then current will pointer the first node in the linked list. This also means that previous will be NULL. We said earlier that previous would be referring to the node whose next pointer needs to be modified in order to complete the removal. In this case, it is not previous but rather the head of the list that needs to be changed.
Line 13 allows us to check the special case described above. If previous didn't move, it will still have the value NULL when the loop breaks. In that case, the head of the list is modified to refer to the node after the current node (line 14), in effect removing the first node from the linked list. However, if previous is not NULL, the node to be removed is somewhere down the linked list structure.
In this case the previous pointer is providing us with the node whose next pointer must be changed. Line 16 modifies and accomplish the removal. Note that in both cases the destination of the pointer change is current->getNext().
You could also add a header node to simplify the process and this is left as exercise.
#include <iostream>
#include "pythonds3/cppds/linked_list.hpp"
using namespace std;
int main() {
UnorderedList<int> myList;
myList.add(31); myList.add(77); myList.add(17);
myList.add(93); myList.add(26); myList.add(54);
cout << myList << endl;
cout << myList.size() << endl;
cout << boolalpha << myList.search(93) << endl;
myList.remove(54);
myList.remove(93);
myList.remove(31);
cout << myList << endl;
return 0;
}
54 26 93 17 77 31
6
true
26 17 77
4.7 The Ordered List Abstract Data Type¶
We will now consider a type of list known as an ordered list. For example, if the list of integers shown in previous section were an ordered list (ascending order), then it could be written as 17, 26, 31, 54, 77, and 93.
The structure of an ordered list is a collection of items where each item holds a relative position that is based upon some underlying characteristic of the item. The ordering is typically either ascending or descending and we assume that list items have a meaningful comparison operation that is already defined.
Many of the ordered list operations are the same as those of the unordered list:
OrderedList()creates an empty ordered list.add(item)inserts while preserving order.remove(item)removes the first match; a missing item is a no-op.search(item)returns a Boolean and may stop after passing the target.
isEmpty()tests whetherhead == NULL.size()counts nodes by traversal.
The teaching header implements this focused interface. Operations such as
positional index and pop belong to a broader list ADT but are not methods of
this OrderedList class.
4.6 Implementing an Ordered Linked List¶
The ordered list of integers given above (17, 26, 31, 54, 77, and 93) can be represented by a linked structure as shown below.
Again, the node and link structure is ideal for representing the relative positioning of the items.
To implement the OrderedList class, we will use the same technique as seen previously with unordered lists. Once again, an empty list will be denoted by a head pointer to NULL:
template <typename T>
class OrderedList {
private:
Node<T> *head;
public:
OrderedList() {
head = NULL;
}
};
isEmpty() and size() are implemented as for UnorderedList. Ordered search() and remove() may stop once a node value exceeds the target; add() must locate the insertion position.
The search() of an unordered linked list required that we traverse the nodes one at a time until we either find the item we are looking for or run out of nodes (NULL).
It turns out that the same approach would work with the ordered list and no changes are necessary if the item is in the list. However, in the case where the item is not in the list, we can take advantage of the ordering to stop the search as soon as possible.
For example, Figure below shows the ordered linked list as a search is looking for the value 45:
The code below shows the complete search() method. It is easy to incorporate the new condition discussed above by adding another check (line 6):
bool search(T item) const {
Node<T> *current = head;
while (current != NULL) {
if (current->getData() == item) {
return true;
} else if (current->getData() > item) {
return false; // passed the spot: stop early!
}
current = current->getNext();
}
return false;
}
Traversal continues while node values are smaller than the target. Once a larger value is seen, the method returns false.
The most significant method modification will take place in add(). Recall that for unordered lists, the add method could simply place a new node at the head of the list. It was the easiest point of access.
Unfortunately, this will no longer work with ordered lists. It is now necessary that we discover the specific place where a new item belongs in the existing ordered list.
Assume we have the ordered list consisting of 17, 26, 54, 77, and 93 and we want to add the value 31. The add method must decide that the new item belongs between 26 and 54:
As we explained earlier, we need to traverse the linked list looking for the place where the new node will be added!
As we saw with unordered lists, it is necessary to have an additional pointer, again called previous, since current will not provide access to the node that must be modified.
void add(T item) {
Node<T> *current = head;
Node<T> *previous = NULL;
while (current != NULL && current->getData() <= item) {
previous = current;
current = current->getNext();
}
Node<T> *newNode = new Node<T>(item);
newNode->setNext(current);
if (previous == NULL) {
head = newNode;
} else {
previous->setNext(newNode);
}
}
The OrderedList class with methods discussed thus far can be found in the repo.
OrderedList::remove uses the ordering to stop early and follows the same erase-if-found contract:
void remove(T item) {
Node<T> *current = head, *previous = NULL;
while (current != NULL && current->getData() < item) {
previous = current;
current = current->getNext();
}
if (current == NULL || current->getData() != item) return;
if (previous == NULL) head = current->getNext();
else previous->setNext(current->getNext());
delete current;
}
#include <iostream>
#include "pythonds3/cppds/linked_list.hpp"
using namespace std;
int main() {
OrderedList<int> myList;
for (int value : {31, 77, 17, 93, 26, 54}) myList.add(value);
cout << myList << endl;
cout << myList.size() << endl;
cout << boolalpha << myList.search(93) << endl;
cout << myList.search(100) << endl;
myList.remove(31);
myList.remove(100); // missing value: no-op
cout << myList << endl;
}
17 26 31 54 77 93
6
true
false
17 26 54 77 93
4.6.1 Analysis of Linked Lists¶
For the exact implementation shown here, isEmpty() is $O(1)$ and size() is
$O(n)$ because no count field is stored. A different implementation that
maintains a size member could make size() $O(1)$, at the cost of updating that
member on every insertion and removal.
Head insertion into UnorderedList is $O(1)$. search(item) and
remove(item) are $O(n)$ in the worst case because they may traverse the whole list. Ordered search can stop early, but its worst case remains $O(n)$. It is noted that add or remove is $O(1)$ once the predecessor iterator/pointer is
already known; locating that position may still cost $O(n)$.
STL Linked Containers: forward_list and list¶
std::forward_list<T> is singly linked and supports push_front, insert_after, and erase_after. std::list<T> is doubly linked and supports bidirectional iterators plus insertion/erasure at an iterator. Neither provides random-access indexing. Constant-time insertion/erasure assumes the relevant iterator is already available.
#include <forward_list>
#include <iostream>
#include <list>
using namespace std;
int main() {
forward_list<int> singly = {31, 54};
singly.insert_after(singly.before_begin(), 17);
list<int> doubly = {17, 31, 54};
auto pos = next(doubly.begin());
doubly.insert(pos, 26);
for (int x : singly) cout << x << ' ';
cout << endl;
for (int x : doubly) cout << x << ' ';
cout << endl;
}
17 31 54
17 26 31 54
The teaching UnorderedList and OrderedList expose pointer mechanics and ownership. In production code, prefer the STL containers: their destructors, copying, iterators, and exception safety are already specified and tested.
A.1 Course Extension: Other Linked Lists¶
Circularly linked list¶
In the case of linked lists, there is a more tangible notion of a circularly linked list, as we can have the tail of the list use its next pointer to point back to the head of the list, as shown below. We call such a structure a circularly linked list.
A circularly linked list provides a more general model than a standard linked list for data sets that are cyclic, that is, which do not have any particular notion of a beginning and end.
A circular view could be used, for example, to describe the order of train stops, or the order in which players take turns during a game. Even though a circularly linked list has no beginning or end, per se, we must maintain a pointer to a particular node in order to make use of the list.
Advance through a circular list with current = current->getNext(). Because there is no NULL terminator, traversal must instead detect when it returns to its start node.
Ideal for efficient resource allocation and management or operation like append()!
Doubly linked list¶
In a singly linked list, each node maintains a pointer to the node that is immediately after it. We have demonstrated the usefulness of such a representation when managing a sequence of elements. However, there are limitations that stem from the asymmetry of a singly linked list.
We emphasized that we can efficiently insert a node at either end of a singly linked list, and can delete a node at the head of a list, but we are unable to efficiently delete a node at the tail of the list.
More generally, we cannot efficiently delete an arbitrary node from an interior position of the list if only given a pointer to that node, because we cannot determine the node that immediately precedes the node to be deleted!
To provide greater symmetry, we define a linked list in which each node keeps an explicit pointer to the node before it and a pointer to the node after it. Such a structure is known as a doubly linked list.
These lists allow a greater variety of $O(1)$-time update operations, including insertions and deletions at arbitrary positions within the list. We continue to use the term next for the pointer to the node that follows another, and we introduce the term prev for the pointer to the node that precedes it.
Ideal for algorithms that require backward traversal (e.g. Palindrome Check)!
A doubly linked list is shown
For a nonempty list, the header's next will refer to a node containing the first real element of a sequence, just as the trailer's prev pointers the node containing the last element of a sequence.
We can treat all insertions in a unified manner, because a new node will always be placed between a pair of existing nodes. In similar fashion, every element that is to be deleted is guaranteed to be stored in a node that has neighbors on each side.
References¶
- Textbook: Problem Solving with Algorithms and Data Structures using C++ (cppds), Chapter 4 (Linked Lists) — https://runestone.academy/ns/books/published/cppds/index.html